public class MaxProfit {
    public int maxProfit(int k, int[] prices) {
        // f[i][j]表示第i天交易次数为j次并且是买入状态时候的最大利润
        // g[i][j]表示第i天交易次数j次并且是卖出状态时候的最大利润
        int len = prices.length;
        int[][] f = new int[len][k+1];
        int[][] g = new int[len][k+1];
        for (int i = 0; i <= k; i++) {
            f[0][i] = -prices[0];
        }
        for (int i = 1; i < len; i++) {
            for (int j = 0; j <= k; j++) {
                f[i][j] = Math.max(f[i-1][j], g[i-1][j] - prices[i]);
                g[i][j] = g[i-1][j];
                if (j-1 >= 0) {
                    g[i][j] = Math.max(g[i][j], f[i-1][j-1] + prices[i]);
                }
            }
        }
        int ret = 0;
        for (int i = 1; i <= k; i++) {
            ret = g[len-1][i];
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] prices = {3,2,6,5,0,3};
        System.out.println(new MaxProfit().maxProfit(2, prices));
    }
}
